문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 쓰레기 수집 (문단 편집) ==== 점진적 쓰레기 수집 ==== 점진적 쓰레기 수집(Incremental Garbage Collection)은 마킹과 해제를 한번에 하지 않고 여러 번에 걸쳐서 수행하는 방식을 말한다. 이렇게 하면 프로그램을 통째로 정지하는 것에 비해 수집과 해제라는 한 사이클에 걸리는 시간은 더 오래 걸릴 수 있지만, 한번 GC를 수행할 때 프로그램이 정지하는 시간은 줄일 수 있다. 위에서 설명한 mark-and-sweep에서도 점진적 쓰레기 수집을 어느 정도 적용 가능하다. 마킹이 끝난 뒤에 접근이 불가능하다고 알려진 메모리는 절대 다시 접근 가능해질 수 없다. 따라서 해당 메모리의 할당 해제는 언제 해도 상관 없으므로 여러번에 걸쳐서 수행해도 된다. 다만, 마킹을 점진적으로 하려면 삼색기법 등의 다른 방법을 동원해야 한다. 삼색기법(tri-color marking)은 기존에 접근 가능/불가능이라는 2가지로만 마킹을 했던 것과 달리 해당 메모리 내부 조사 여부에 따라 추가적으로 나눠서 3가지로 마킹한다. 보통은 접근 가능한지 알 수 없는 메모리를 흰색, 접근 가능하지만 해당하는 메모리에서 참조하는 메모리의 마킹을 하지 않은 경우 회색, 접근 가능하며 해당 메모리가 참조하는 메모리의 마킹도 끝났으면 검은색으로 마킹을 한다. 처음에는 root를 조사하다가 흰색인 메모리를 발견하면 회색으로 마킹을 한다. root를 모두 마킹했으면 회색으로 마킹된 메모리를 조사하여 해당 메모리가 참조하는 모든 메모리를 회색으로 마킹을 한다. 이 작업이 끝나면 처음 회색이었던 메모리를 검은색으로 바꾼다. 만약 회색으로 마킹된 메모리가 존재하지 않으면 모두 흰색이나 검은색일 것이고, 접근 가능 여부가 결정된다. 이런 식으로 하면 임의로 GC를 중단하여도 다음번에 회색인 메모리부터 다시 조사하면 되므로 여러번에 걸쳐서 GC를 수행할 수 있다. 하지만 이 경우에도 마킹과 마킹 중간에 메모리 내의 참조가 수정이 되면 잘못 마킹되는 것이 생길 수가 있다. 예를 들어서 root가 A를, A가 B를 참조하며, A 외에 B로 접근 가능한 메모리가 없다고 하자. 이 상태에서 GC를 수행하여 A, B가 검은색으로 마킹되고 GC가 정지했다고 하자. 이후 다시 GC가 수행되면 할당 해제를 해야하는데, 다음 GC 수행 전에 흰색으로 마킹된 상태인 C에 대해, A가 B에 대한 참조를 제거하고 C를 참조하게 바꾼다고 해보자. 그러면 B는 접근이 불가능한데 검은색이고 C는 접근 가능한데 흰색이다. 이 문제를 해결하기 위해 보통은 read-barrier나 write-barrier를 사용하여 root 메모리에 읽거나 쓰는 것에 제약을 둔다. 보통은 읽는 것보다는 쓰는 것이 적게 일어나므로 write-barrier가 사용된다. 예시로 위의 경우에는 A의 참조가 C가 되도록 씌어진 것이므로, C의 마킹을 회색으로 바꾸면 된다. 그러면 B는 당장 할당해제 되지는 않지만 적어도 C가 해제되는 일은 없앨 수 있다. 마킹을 하지 않고 아예 메모리를 옮겨버리는 방법도 있다. Cheney's Algorithm이 바로 그 대표적인 예시이자 대표적인 Copying GC 알고리즘이다. 이 방식은 처음에 메모리를 두 개의 같은 크기의 공간으로 나눠서 할당을 하고 시작한다. 하나를 A, 하나를 B라고 하면, 처음에는 모든 메모리를 A에 할당을 한다. 그러다가 A가 가득 차는 등으로 인해 GC가 실행되면 A에서 접근 가능한 메모리를 전부 B로 복사한다. 이 과정이 끝나면 B에는 A에서 접근 가능한 메모리들의 사본만이 있게 되고 A는 메모리를 비워버린다. 그 다음에는 B에 할당을 하다가 GC가 실행되면 A로 복사하고...를 반복하게 된다. 이 방식에서도 조사 중 접근 가능한 것을 바로바로 옮겨버리면 어디까지 조사했는지 알 수 있으므로 점진적으로 GC를 수행할 수 있다. 가장 큰 장점은 메모리를 재배열 할 수 있다는 것이다. 물론 위 삼색기법도 메모리 재배열이 불가능한 것은 아니지만, 이 방식은 GC가 완료되면 새로운 공간에 단편화 없이, 접근 가능한 순서에 가깝게 재배열이 되기에 캐시 효율이 높아지게 된다. 그러다보니 세대별 GC와 같이 비교적 많이 사용되는 방식이다. 또한 아예 메모리를 할당해두고 시작하기 때문에 힙 영역의 메모리 할당을 스택처럼 빠르게 할 수 있다는 장점도 있다. 하지만 메모리 공간을 많이 사용하게 되며, 복사를 해야되기 때문에 메모리의 주소가 바뀌어 버리므로 포인터를 이용한 접근을 포기하거나 주소 바뀔 때마다 모든 메모리의 주소를 갱신해야하며, 복사하는 과정에서의 오버헤드도 무시하긴 힘들다는 단점도 있다. 이 방법을 이상하게(?) 활용하는 경우가 바로 [[Scheme]]의 R5RS 구현체 중 하나인 Chicken Scheme이다.[[http://home.pipeline.com/~hbaker1/CheneyMTA.html|#]] 이 녀석의 특징이라면 함수를 호출만 하고 리턴을 하지 않은 채로 콜스택에 계속 쌓는다. 보통 힙에 동적할당 하는 것도 alloca등을 이용해서 스택에 정적할당 시켜버리는 방식을 사용한다. 그러다가 스택이 터지기 직전쯤에 이걸 중단하고 다음에 호출할 함수들을 longjmp로 호출을 시작한 스택프레임까지 점프해버린다. 이 때 스택에 있는 메모리에 대해 GC를 실행하여 살아있는 객체들을 힙으로 옮기게 된다. 이렇게 하는 이유는 몇가지 있는데, C 표준에서 꼬리 재귀 최적화를 지원하지 않다보니 이를 trampoline[* 다른 함수를 순서대로 계속 호출해주는 함수를 만들고, 그 내부에서 실행되는 함수가 다음에 호출되는 함수를 반환해서 꼬리재귀를 구현하는 방식] 없이 구현하기 위함도 있고, 아래의 세대별 GC를 구현하기 위한 것도 있다.저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기